//	ID : pallab81
// 	PROG : 11730
// 	LANG : C++
// 	2011-07-28-21.54.41 Thursday
//
// 	"I have not failed, I have just found 10000 ways that won't work.
//


#include <iostream>
#include <algorithm>
#include <vector>
#include <sstream>
#include <fstream>
#include <string>
#include <list>
#include <map>
#include <set>
#include <queue>
#include <stack>
#include <functional>
#include <bitset>

#include <cassert>
#include <cstdio>
#include <cmath>
#include <cstring>
#include <climits>
#include <cstring>

using namespace std;

#define fo(i,ed) for(int i = 0 ; i < ed ; ++i )
#define foit(i, x) for (typeof((x).begin()) i = (x).begin(); i != (x).end(); i++)
#define bip system("pause")
#define Int long long
#define pb push_back
#define SZ(X) (int)(X).size()
#define LN(X) (int)(X).length()
#define mk make_pair
#define num first
#define step second
#define SET( ARRAY , VALUE ) memset( ARRAY , VALUE , sizeof(ARRAY) )

const int inf = (int)1023456789;
int S,T;
int cases;
vector< int > vis;
inline vector<int> prime_factors(int x){
    int i;
    int _x = x;
    vector< int > fact;
    for( i=2; i*i <=x ; ++i ){
        if( x%i ==0 ){
            while( x%i ==0 ){
                x/=i;
            }
            fact.pb(i);
        }
    }
    if( x>1 && x!=_x ){
        fact.pb(x);
    }
return fact;
}
inline int bfs(int s, int sink){
    if(s==sink){
        return 0;
    }
    vis.assign(8000, inf);
    queue< pair<int,int> > q;
    q.push( mk(s,0) );
    vis[ s ] = 0;

    while( q.empty()==false ){
        pair<int,int> peak = q.front();
        q.pop();

            vector< int > p_fact = prime_factors(peak.num);
            fo(i,SZ(p_fact)){
                int _num = p_fact[i] + peak.num;
                int _step = peak.step+1;
                if( _num > sink )continue;
                if( _num == sink ){
                    return _step;
                }
                if( _step < vis[ _num ] ){
                    vis[ _num ] = _step;
                    q.push( mk(_num, _step ) );
                }

            }

    }

return -1;
}
inline void proc(){
    int var = bfs(S,T);
    printf("Case %d: %d\n",cases,var);
}

int main(){
    #ifndef ONLINE_JUDGE
        freopen("in.txt","rt",stdin);
    #endif
    cases=1;
    while( scanf("%d %d",&S,&T)==2 ){
        if( S==0 && T==0 )break;
        proc();
        ++cases;
    }

return 0;
}


